'''
Created on Jul 31, 2011

@author: User
'''

from graphUtils.scenarioGenerator import ScenarioGenerator
import cliques.utils
import math
import graph
from cliques.cliqueFinder import cliqueFinder
from scenario import Scenario

class CliqueScenarioGenerator(ScenarioGenerator): 
    '''
    Creates graph with cliques
    '''

    def __init__(self, base_folder):
        ScenarioGenerator.__init__(self, base_folder)
     
    def __generate_graph(self,nodes,edge_prob):
        ''' Creates a random graph '''
        new_graph = graph.graph()    
        edges_in_full_graph = ((nodes*(nodes-1))/2)        
        new_graph.generate(nodes, int(math.ceil(edge_prob*edges_in_full_graph))) # The plus one is a debatable hack to round up
        return new_graph     
        
    def generate(self, nodes, expected_cliques, clique_size):
        ''' Generate a random graph with the given nodes and edges, 
        and with a clique of the given size '''
        edges_in_clique = clique_size*(clique_size-1)/2  # Assuming the graph is undirected
        
        possible_cliques = 1.0*cliques.utils.binomial(nodes, clique_size)
                
        edge_prob = math.pow(expected_cliques/possible_cliques,1.0/edges_in_clique)
                
        exp_graph = self.__generate_graph(nodes, edge_prob)
        start_node = cliques.utils.choose_random_node(exp_graph)
               
        clique_finder = cliqueFinder()
        clique_finder.setup(exp_graph)
        
        # Check if contains a k-clique is start_node's connected component
        connected_comp = exp_graph.connected_components()
        comp_index = connected_comp[start_node]
        comp_items = [item for item in connected_comp.keys() if connected_comp[item]==comp_index]
        k_clique_exists = clique_finder.has_clique(clique_size, comp_items)
        if k_clique_exists:
            return Scenario(exp_graph, start_node) 
        else:
            return None
      